/**
 * 二叉排序树t
 * 查找第k小的元素，返回指针，要求平均查找时间为O(log2_n)
 * 这个tree的每个节点有一个额外的count字段表示当前节点为根的树有多少个节点
 */

#include "BiTree.h"
class Tree
{
public:
    int count=0;//表示当前节点为根的节点个数
    int val;
    struct Tree * left;
    struct Tree * right;
};

/**
 * 当t.left为空的时候
 * 若t.right非空且k==1，则t就是第k小的元素，查找成功
 * 若t.right非空且k!=1，则k小的元素必定在t的右子树
 * 
 * 当t.left非空时
 * t.left.count==k-1 t就是第k小的元素，查找成功
 * t.left.count>k-1 k小的元素必定在t的左子树，继续在t的左子树查找
 * t.left.count<k-1 k小的           右   ，寻找第k-(t.left.count+1)小的元素
 */

Tree *search_k(Tree* t,int k){
    if(k<1||k>t->count) return nullptr;
    if(t->left==nullptr){
        if(k==1) return t; //如果左子树为空，且k=1 ，那么当前元素就是第k=1个元素返回自己
        else return search_k(t->right,k-1);//左子树为空，且自己k!=1，那么要从右子树查找，因为自己已经被检查过了，那么要从右子树找第k-1个元素
    }else{
        if(t->left->count==k-1)return t; //t的左子树有k-1个元素，那么当前这个元素就是第k个元素，返回自己
        if(t->left->count>k-1)return search_k(t->left,k);
        if(t->left->count<k-1) return search_k(t->right,k-(t->left->count+1));//这里k要减去的就是当前节点的左子树节点个数加上他自己，然后从右子树查找
    }
}